package com.atguigu.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @author shkstart
 * @create 2021-08-15 23:35
 */
//时间复杂度O(n^2)
//该台电脑使用时间：1秒左右
public class InsertSort {
    public static void main(String[] args) {
//        int arr[]={101,34,119,1};
//       insertSort(arr);
//        System.out.println(Arrays.toString(arr));
        int[] arr = new int[800000];
        for (int i=0;i<80000;i++){
            arr[i]=(int)(Math.random()*800000);
        }
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String format = simpleDateFormat.format(date1);
        System.out.println("排序前的时间="+format);

        insertSort(arr);
//        System.out.println(Arrays.toString(arr));
        Date date2 = new Date();
//        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String format2 = simpleDateFormat.format(date2);
        System.out.println("排序后的时间="+format2);
    }
//    public static void insertSort(int [] arr){
//        int insertVal=0;
//        int insertIndex=0;
//        //从一开始
//        for (int i=1;i<arr.length;i++){
//            //把要加入的值保存下来
//            insertVal=arr[i];
//            //索引减一，与之前一位进行比较
//            insertIndex=i-1;
//            //要插入的值与之前的序列进行一一比较
//            while (insertIndex>=0 && arr[insertIndex]>insertVal){
//                arr[insertIndex+1]=arr[insertIndex];
//                insertIndex--;
//            }
//            //最后找到对应的位置，跳出循环，赋值
//            //优化
//            if (insertIndex+1!=i) {
//                arr[insertIndex + 1] = insertVal;
//            }
//        }
//    }
    public static void insertSort(int[] arr){
        int j;
        for (int p=1;p<arr.length;p++){
            int tem=arr[p];
            for (j=p;j>0&&tem<arr[j-1];j--){
                arr[j]=arr[j-1];
            }
            arr[j]=tem;
        }
    }
}
